#include <iostream>
using namespace std;
struct BinaryTreeDate
{
	BinaryTreeDate *parent;
	BinaryTreeDate *left;
	int key;
	BinaryTreeDate *right;
	BinaryTreeDate(int Key) :key(Key), left(nullptr), right(nullptr), parent(nullptr){}
};

void Fun(BinaryTreeDate * &Root)
{
	while (Root->left != nullptr || Root->right != nullptr)
	{
		while (Root->left != nullptr)
			Root = Root->left;

		while (Root->right != nullptr)
			Root = Root->right;
	}
}

void swap(BinaryTreeDate *Root, BinaryTreeDate *Node)
{
	BinaryTreeDate *Left_l = Node->left;
	BinaryTreeDate *Right_l = Node->right;
	BinaryTreeDate *parent = Root->parent;
	if (Left_l != nullptr)
		Left_l->parent = Root;
	if (Right_l != nullptr)
		Right_l->parent = Root;
	Node->parent = Root->parent;
	Node->left = Root;
	if (Node == Root->left)
		Node->right = Root->right;
	else
		Node->right = Root->left;
	Root->parent = Node;
	Root->left = Left_l;
	Root->right = Right_l;
	if (parent != nullptr)
	{
		if (parent->left == Root)
			parent->left = Node;
		else
			parent->right = Node;
	}
}

void Change(BinaryTreeDate *&Root, BinaryTreeDate *&left, BinaryTreeDate *&right)
{
	swap(Root, left);
	right->parent = left;
}

BinaryTreeDate *CheckAndChange(BinaryTreeDate * &Root)
{
	if (Root == nullptr)
		return nullptr;

	//只检测此一个节点是否符合最小堆性质，不符合则改变
	BinaryTreeDate *left = Root->left;
	BinaryTreeDate *right = Root->right;

	if (left == nullptr && left == right)
		return Root;
	else
	if (left != nullptr && right != nullptr)
	{
		if (Root->key <= left->key && Root->key <= right->key)
			return Root;//表示符合

		//左边结点小
		if (left->key < Root->key && left->key <= right->key)
		{
			Change(Root, left, right);
			return left;
		}
		else//右边结点小
		if (right->key < Root->key && right->key <= left->key)
		{
			Change(Root, right, left);
			return right;
		}
	}else
	if (left != nullptr && left->key < Root->key)
	{
		//表示right == nullptr
		swap(Root, left);
		return left;
	}else
	if (right != nullptr && right->key < Root->key	)
	{
		//表示left == nullptr
		swap(Root, right);
		return right;
	}
	return Root;
}

BinaryTreeDate *CreateMinLinkHeap(BinaryTreeDate *& Node)
{
	BinaryTreeDate *Root = Node;
	Fun(Root);
	while (Root && Root->parent != nullptr)
	{
		if (Root != Root->parent->right)
		{
			if (Root->parent->right != nullptr)
			{
				Root = Root->parent->right;
				Fun(Root);
			}
			else
				Root = CheckAndChange(Root->parent);
		}
		else
		{
			if (Root->parent != nullptr)
				Root = CheckAndChange(Root->parent);
		}
	}
	return Root;
}

int main()
{
	BinaryTreeDate *Root = new BinaryTreeDate(20);
	BinaryTreeDate *p1 = new BinaryTreeDate(10);
	Root->left = p1;
	p1->parent = Root;
	BinaryTreeDate *p2 = new BinaryTreeDate(12);
	Root->right = p2;
	p2->parent = Root;
	BinaryTreeDate *p3 = new BinaryTreeDate(21);
	p2->left = p3;
	p3->parent = p2;
	BinaryTreeDate *p4 = new BinaryTreeDate(4);
	p2->right = p4;
	p4->parent = p2;

	BinaryTreeDate *p5 = new BinaryTreeDate(6);
	p1->left = p5;
	p5->parent = p1;
	BinaryTreeDate *p6 = new BinaryTreeDate(2);
	p1->right = p6;
	p6->parent = p1;
	BinaryTreeDate *p7 = new BinaryTreeDate(9 );
	p4->left = p7;
	p7->parent = p4;
 	BinaryTreeDate *Root1 = CreateMinLinkHeap(Root);
	Root1 = CreateMinLinkHeap(Root1);
	Root1 = CreateMinLinkHeap(Root1);
	//暂时只测试到这里，不过总体表现为，只需循环n-1次,其中n与树的最大深度有关CreateMinLinkHeap
	//不过总结来说，最坏情况为O(N^2)
	delete Root;
	delete p1;
	delete p2;
	delete p3;
	delete p4;
	delete p5;
	delete p6;
	return 0;
}